package leetcode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordLadder {

	//Basically I keep two sets of words,
	//one set reached that represents the borders that have been reached with "distance" steps
	
	//In the while loop, for each word in the reached set, I give all variations and 
	//check if it matches anything from wordDict
	//if it has a match, I add that word into toAdd set, which will be my "reached" set in the next loop
	
	//unfortunately，I got TLE!!!
	//fortunately, I find the reason.
	public int ladderLength2(String beginWord, String endWord,
			List<String> wordDictList) {
		if(wordDictList == null){
			return 0;
		}
		Set<String> wordDict = new HashSet<>(wordDictList);
		if(!wordDict.contains(endWord)){
			return 0;
		}
		//当前得到的单词
		List<String> reached = new ArrayList<String>();
		reached.add(beginWord);
		wordDict.add(endWord);
		int distance = 1;
		
		//比如hit -> hot -> cot -> cog
		//hit -> hig -> dig -> dog -> cog
		//我们只需要一步一步的获取到所有能够到达的单词，一旦发现有endWord
		//此时肯定是最小的
		while (!reached.contains(endWord)) {
			//toAdd表示当前reached的单词能够变换的得到在字典中的单词
			List<String> toAdd = new ArrayList<String>();
			for (String each : reached) {
				for (int i = 0; i < each.length(); i++) {
					char[] chars = each.toCharArray();
					
					//将i从a变到z，逐个判断是否在字典中
					for (char ch = 'a'; ch <= 'z'; ch++) {
						chars[i] = ch;
						String word = new String(chars);
						
						//alright, I finally find the reason why got TLE
						//I use the list to judge if it contains word, it's O(n)
						//while I change it to set, which is implements by hashmap, so it's O(1)
						
						if (wordDict.contains(word)) {
							toAdd.add(word);
							wordDict.remove(word);
						}
					}
				}
			}
			distance++;
			//which means that if I can't reach any new String from wordDict, I absolutely can't
			//reach the endWord
			if (toAdd.size() == 0)
				return 0;
			reached = toAdd;
		}
		// Finally if the endWord is in reached set, I return the current steps "distance"
		return distance;
	}
	
	
	//apparently, ablve sollution has a high time complexy
	
	//Two - end BFS
	public int ladderLength(String beginWord, String endWord, List<String> wordAsList) {
		//why should we use the set rather than list?
		//searching a word in the String set is O(1) operation
		
		Set<String> wordList = new HashSet<String>(wordAsList);
        Set<String> start = new HashSet<String>();
        Set<String> end = new HashSet<String>();
        int length = 1;
        start.add(beginWord); end.add(endWord);
        wordList.remove(beginWord); wordList.remove(endWord);
        
        
		while (!start.isEmpty()) {
			Set<String> next = new HashSet<String>();
			for (String word : start) {
				char[] wordArray = word.toCharArray();
				for (int i = 0; i < word.length(); i++) {
					char old = wordArray[i];
					for (char c = 'a'; c <= 'z'; c++) {
						wordArray[i] = c;
						String str = String.valueOf(wordArray);
						if (end.contains(str))
							return length + 1;
						if (wordList.contains(str)) {
							next.add(str);
							wordList.remove(str);
						}
					}
					//还原
					wordArray[i] = old;
				}
			}
			//key point: as we see in the above solution, we just use start = next
			//why do we judge the length in this solution?
			//this maybe is the means of two - ends 
			
			//got it, the key point is a -> b is same as b -> a
			//if next's size is less than end, start = end, else start = end 
			//and end is end or next depends on start which is next ,end is end; which is end, end is next
			
			start = next.size() < end.size() ? next : end;
			end = start.size() < end.size() ? end : next;
			length++;
		}
		
		return 0;
	}
}
